/*
Source : https://leetcode.com/problems/merge-two-sorted-lists/
Author : nflush@outlook.com
Date   : 2016-07-22
*/

/*
21. Merge Two Sorted Lists
 ?  

Question Editorial Solution  
 My Submissions 




?Total Accepted: 140817
?Total Submissions: 387825
?Difficulty: Easy



Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.



Subscribe to see which companies asked this question


Show Tags
 

Show Similar Problems
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 // 12ms
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head;
        ListNode **tail = &head;
        while (l1 && l2){
            if (l1->val < l2->val){
                *tail = l1;
                tail = &l1->next;
                l1 = l1->next;
            } else {
                *tail = l2;
                tail = &l2->next;
                l2 = l2->next;
            }
        }
        *tail = l1 ? l1: l2;
        return head;
    }
};

// 8ms
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head(0);
        ListNode *tail = &head;
        while (l1 && l2){
            if (l1->val < l2->val){
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1 ? l1: l2;
        return head.next;
    }
};

// 12ms
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head(0);
        ListNode *tail = &head;
        while (l1 && l2){
            if (l1->val < l2->val){
                tail->next = l1;
                do {
                    l1 = l1->next;
                    tail = tail->next;
                } while(l1 && l1->val <= l2->val);
                
            } else {
                tail->next = l2;
                do {
                    l2 = l2->next;
                    tail = tail->next;
                } while(l2 && l2->val <= l1->val);
            }
        }
        tail->next = l1 ? l1: l2;
        return head.next;
    }
};

// 8ms
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head(0);
        ListNode *tail = &head;
        while (l1 && l2){
            if (l1->val < l2->val){
                ListNode *x = l1;
                ListNode *t = l1;
                do {
                    t = l1;
                    l1 = l1->next;
                }while(l1 && l1->val <= l2->val);
                tail->next = x;
                tail = t;
            } else {
                tail->next = l2;
                l2 = l2->next;
                tail = tail->next;
            }
        }
        tail->next = l1 ? l1: l2;
        return head.next;
    }
};

